package leetcode.sword;

public class Solution12_new {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        int rowNum = board.length;
        int colNum = board[0].length;
        String word = "ABCCED";
        int[][] directs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if(findWordInBoard(board, i, j, word,0, directs)){
                    System.out.println(true);
                }
            }
        }
        System.out.println(false);
    }

    public static boolean findWordInBoard(char[][] board, int starti, int startj, String word, int wordi, int[][] directs){
        /**
         * 用于递归查找的函数，starti, startj是当前开始对比的board格子下标，wordi是当前要对比的word字符下标
         */
        if(starti<0 || starti>board.length-1 || startj<0 || startj>board[0].length-1){ //搜索到board边界了
            return false;
        }
        if(board[starti][startj]=='1'){ //当前格子已被搜索过
            return false;
        }
        if(board[starti][startj]!=word.charAt(wordi)) {//当前格子和要查找的word元素不同
            return false;
        }
        //收割一波:当前格子和要查找的word元素相同
        if (wordi == word.length()-1) { //word已被全部找到
            return true;
        }
        //进入回溯
        char tmp = board[starti][startj];
        board[starti][startj] = '1'; //向附近查找前先把当前格子设为禁忌，防止回溯
        //word还没找齐，从当前格子向附近继续查找
        for (int[] direct : directs) {
            if(findWordInBoard(board,starti+direct[0],startj+direct[1],word,wordi+1,directs)){
                return true;
            }
        }
        //上下左右都找不齐
        board[starti][startj] = tmp; //放开禁忌
        return false;
    }
}